class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    /*
    标记数组vis表示哪些数已经入栈，要满足字典序最大所以第一个出栈元素一定是n
    当最大数n入栈，n--，
    */
    vector<int> solve(int* a, int aLen) {
        // write code here
        stack<int>s;
        int n=aLen;
        vector<int>ans;
        vector<int>vis(aLen+1,0);//标记数组，每压入一个元素就标记为1
        for(int i=0;i<aLen;i++)
        {
            s.push(a[i]);
            vis[a[i]]=1;
            while(n&&vis[n]) n--; //栈中较大的数出现了
            while(!s.empty()&&n<=s.top()) //依次将大数出栈
            {
                ans.push_back(s.top());
                s.pop();
            }
        }
        while(!s.empty())
        {
            int tmp=s.top();
            ans.push_back(tmp);
            s.pop();
        }
        return ans;
    }
};